using System;
using FineCollection.Intf;



namespace FineCollection.Cont
{
    /// <summary>
    /// A map that keeps the order of K->V pairs,
    /// and with index-based access to this pairs.
    /// </summary>
    /// <remarks>
    /// Note: removing non-last pair from this array can be a hard operation.
    /// </remarks>
    /// <typeparam name="K">key type.</typeparam>
    /// <typeparam name="V">values type.</typeparam>
    public class ArrMap<K, V> : ArrBaseCollection<MapEntry<K, V>>, RRandomList<MapEntry<K, V>>, WMap<K,V>
        where K: IEquatable<K>
    {

        /// <summary>
        /// Count of pairs in the array when a hash table is created (if not yet).
        /// </summary>
        private const int UseHashTableThreasold = 7;

        /// <summary>
        /// Count of pairs in the array when a hash tables is dropped (if exists).
        /// </summary>
        private const int UnuseHashTableThreasold = 3;


        private HashMap<K,int> hashMap;


        /// <summary>
        /// Constructs an empty array-based map.
        /// </summary>
        public ArrMap() 
            : base(1)
        {}


        /// <summary>
        /// Constructs an empty array-based map.
        /// </summary>
        /// <param name="firstIndex">origin index (index of the first item).</param>
        public ArrMap(int firstIndex) 
            : base(firstIndex)
        {}


        /// <summary>
        /// Constructs an empty array-based map with the specified capacity.
        /// </summary>
        /// <param name="firstIndex">origin index (index of the first item).</param>
        /// <param name="cap">neccessary capacity.</param>
        public ArrMap(int firstIndex, int cap)
            : base(firstIndex, cap)
        {}



        /// <summary>
        /// Represents a quick read-only indexed access to the map.
        /// </summary>
        /// <remarks>
        /// The given index must be in [ <c>FirstIndex</c> .. <c>LastIndex</c> ] inclusive.
        /// </remarks>
        /// <param name="index">index of pair to access.</param>
        /// <exception cref="CollectionIsEmptyException">when the collection is empty.</exception>
        /// <exception cref="IndexOutOfBoundsException">when index is incorrect.</exception>
        /// <seealso cref="RRandomList{T}.FirstIndex"/>
        /// <seealso cref="RRandomList{T}.LastIndex"/>
        public new MapEntry<K, V> this[int index]
        {
            get 
            {           
                int intIndex = CalcInternalIndex(index);
                return ar[intIndex];
            }
        }


        public bool ContainsKey(K key)
        {
            if (hashMap != null)
            {
                return hashMap.ContainsKey(key);
            }
            else
            {        
                for (int i = 0; i < count; i++)
                    if (ar[i].Key.Equals(key))
                        return true;
                return false;
            }
        }


        /// <summary>
        /// Looks for the specified key in the map,
        /// and returns an index of this key.
        /// </summary>
        /// <param name="key">key to look for.</param>
        /// <returns>index of the key, or <c>int.MinValue</c> if not found.</returns>
        public int FindKey(K key)
        {
            if (hashMap != null)
            {
                return hashMap.Find(key, int.MinValue);
            }
            else
            {
                for (int i = 0; i < count; i++)
                    if (ar[i].Key.Equals(key))
                        return firstIndex + i;
                return int.MinValue;
            }
        }


        /// <summary>
        /// Looks for the pair with the specified key.
        /// </summary>
        /// <param name="key">key to look for.</param>
        /// <param name="notFound">value that should be returned when the specified key is not found.</param>
        /// <returns>the associated value, of <c>notFound</c> when the key is not found.</returns>
        public V Find(K key, V notFound)
        {
            if (hashMap != null)
            {
                int index = hashMap.Find(key, int.MinValue);
                if (index > int.MinValue)
                    return base[index].Value;
                else
                    return notFound;
            }
            else
            {
                for (int i = 0; i < count; i++)
                    if (ar[i].Key.Equals(key))
                        return ar[i].Value;
                return notFound;
            }
        }


        public MapEntry<K, V>[] ListAllEntries()
        {
            MapEntry<K,V>[] result = new MapEntry<K, V>[count];
            Array.Copy(ar, result, count);
            return result;
        }


        public void Include(K key, V value)
        {
            if (ContainsKey(key))
                throw new DuplicatesFoundException("The key \"" + key + "\" already exists in the map.");

            InternalAddItem(new MapEntry<K, V>(key,value));

            if (hashMap == null)
            {
                if (count >= UseHashTableThreasold)
                    BuildHashTable();
            }
            else
            {
                hashMap.Include(key, lastIndex);
            }
        }

        private void BuildHashTable()
        {
            hashMap = new HashMap<K, int>();
            for (int i = firstIndex; i <= lastIndex; i++)
                hashMap.Include(base[i].Key, i);
        }


        public V Exclude(K key)
        {
            int index = FindKey(key);
            if (index == int.MinValue) return default(V);

            V value = base[index].Value;
            RemoveElementAt(index);

            if (hashMap != null)
            {
                if (count <= UnuseHashTableThreasold)
                {
                    hashMap = null;
                }
                else
                {
                    hashMap.Exclude(key);

                    // todo reimplement using LinkedListImp.ProcessAll
                    for (int j = index; j <= lastIndex; j++)
                    {
                        K theKey = base[j].Key;
                        hashMap[theKey] = j;
                    }
                }
            }

            return value;
        }


        public override void Clear()
        {
            base.Clear();
            hashMap = null;
        }


        V RMap<K, V>.this[K key]
        {
            get
            {
                return Find(key, default(V));
            }
        }


        public V this[K key]
        {
            get 
            { 
                return Find(key, default(V)); 
            }

            set
            {
                int index = FindKey(key);
                if (index == int.MinValue)
                    Include(key, value);
                else
                    ar[index - firstIndex].Value = value;
            }
        }
    }
}